package binarysearch;

import org.junit.Test;

public class ArrangeCoins441 {

    @Test
    public void test() {
        System.out.println(Integer.MAX_VALUE); //2147483647
        System.out.println(arrangeCoins(1));
        System.out.println(arrangeCoins(2));
        System.out.println(arrangeCoins(3));
        System.out.println(arrangeCoins(4));
        System.out.println(arrangeCoins(5));
        System.out.println(arrangeCoins(6));
        System.out.println(arrangeCoins(7));
        System.out.println(arrangeCoins(8));
        System.out.println(arrangeCoins(1804289383));
    }

    public int arrangeCoins(int n) {
        System.out.println("--------------");
        if (n <= 1) {
            return n;
        }
        int l = 0;
        int r = n;
        while (l <= r) {
            int m = l + (r - l)/2;
            // avoid 2*n overflow
            int t = (int) (2 * (long)n / m);
            System.out.format("n: %d, L: %d, R: %d, M: %d, t: %d\n", n, l, r, m, t);
            if (t > m + 1) {
                l = m + 1;
            } else if (t < m + 1) {
                r = m - 1;
            } else {
                return m;
            }
        }
        return r;
    }
}
